package mid.class1;

import cn.hutool.core.util.ArrayUtil;
import common.ArrayUtils;

import java.util.Arrays;

/**
 * 用静态数组实现前缀树
 * 数据结构
 * 输入：{abcdc,afd}
 * * 	a b c d e f g h
 * * 0 	1 2 3 4 5 6 7 8
 * * 0 	0 0 0 0 0 0 0 0 ... 25 无效行
 * * 1 	2 0 0 0 0 0 0 0
 * * 2 	0 3 0 0 0 7 0 0
 * * 3 	0 0 4 0 0 0 0 0
 * * 4 	0 0 0 5 0 0 0 0
 * * 5 	0 0 6 0 0 0 0 0
 * * 6 	0 0 0 0 0 0 0 0
 * * 7	0 0 0 8 0 0 0 0
 * * 8  0 0 0 0 0 0 0 0
 * * tree中结果： str1:a b c d c   str2:a f d
 * *             	 2 3 4 5 6	      2 7 8
 * *
 */
public class Code02_TrieTree02 {


    public static void main(String[] args) {
        String[] arr = {"apple", "abc", "app", "cba", "cca"};
//        String[] arr = {"abcdc", "afd"};
//        String[] arr = {"cba", "cbb", "cbe", "cbs", "cba", "fk"};
        ArrayTrie trie = new ArrayTrie();
        trie.printTitle();
        for (int i = 0; i < arr.length; i++) {
            trie.insert(arr[i]);
        }
        ArrayUtils.printMatrixArr(trie.tree);
        System.out.println("pas = " + ArrayUtil.toString(Arrays.copyOf(trie.pass, 40)));
        System.out.println("end = " + ArrayUtil.toString(Arrays.copyOf(trie.end, 40)));
        int cba = trie.search("cba");
        System.out.println("cba = " + cba);
        int cb = trie.prefixNumber("cb");
        System.out.println("cb = " + cb);
        trie.delete("abc");
        int abc = trie.search("abc");
        System.out.println("abc = " + abc);
    }


    static class ArrayTrie {

        private int m = 20;
        private int[][] tree = new int[m][26];
        private int[] pass = new int[m];
        private int[] end = new int[m];
        private int cnt = 0;

        public ArrayTrie() {
            this.cnt = 1;
        }

        public void printTitle() {
            System.out.print("  [ ");
            for (int i = 0; i < 25; i++) {
                System.out.print((char) (97 + i) + "  ");
            }
            System.out.print("  ]");
            System.out.println();
        }

        public void insert(String str) {
            int cur = 1;
            pass[cur]++;
            for (int i = 0; i < str.length(); i++) {
                int path = str.charAt(i) - 'a';
                if (tree[cur][path] == 0) {
                    tree[cur][path] = ++cnt;
                }
                cur = tree[cur][path];
                pass[cur]++;
            }
            end[cur]++;
        }

        public int prefixNumber(String str) {
            int cur = 1;
            for (int i = 0; i < str.length(); i++) {
                int index = str.charAt(i) - 'a';
                if (tree[cur][index] == 0) {
                    return 0;
                }
                cur = tree[cur][index];
            }
            return pass[cur];
        }

        public int search(String str) {
            int cur = 1;
            for (int i = 0; i < str.length(); i++) {
                int index = str.charAt(i) - 'a';
                if (tree[cur][index] == 0) {
                    return 0;
                }
                cur = tree[cur][index];
            }
            return end[cur];
        }

        public void delete(String str) {
            if (search(str) > 0) {
                int cur = 1;
                for (int i = 0; i < str.length(); i++) {
                    int path = str.charAt(i) - 'a';
                    if (--pass[tree[cur][path]] == 0) {
                        tree[cur][path] = 0;
                        return;
                    }
                    cur = tree[cur][path];
                }
                end[cur]--;
            }
        }

        /**
         * 清除时不要忘end和pass数组
         */
        public void clear() {
            for (int i = 0; i < cnt; i++) {
                Arrays.fill(tree[i], 0);
                end[i] = 0;
                pass[i] = 0;
            }
        }

    }


}
